package leetcode;

import java.util.Arrays;
import java.util.HashMap;

/*

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

序号从 1 开始编号。
一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
每个数字的序号都应该尽可能地小。

思路：
1.对整个数组排序
2.遍历整个排序数组，对重复的数字跳过,存入hash表
3.第二次遍历数组，记录数组排序
 */
public class Test1331 {

    public int[] arrayRankTransform(int[] arr) {
        // 找到最大最小值

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        // 构造向量数组
        int[] count = new int[max - min + 1];
        // 存在的数标记为1不存在的为0
        for (int num : arr){
            count[num - min] = 1;
        }
        int[] preSum = new int[count.length + 1];

        // 对存在数标记排序
        int index=0;
        for(int i=0;i<count.length;i++){
            if(count[i]>0)
                index++;
            preSum[i]=index;
        }


        int[] target=new int[arr.length];
        for(int i=0;i<arr.length;i++){
            target[i]=preSum[arr[i]-min];
        }

        return target;
    }
}
